UVa/10034 - Freckles/p10034.cpp

   1 #include <iostream>
   2 #include <cmath>
   3 #include <map>
   4 #include <queue>
   5 #include <set>
   6
   7 using namespace std;
   8
   9 typedef pair<double, double> point;
  10 //Gives a vector of adjacent nodes to a point
  11 typedef map< point, vector<point> > graph;
  12 //Edge of length "first" that arrives to point "second"
  13 typedef pair<double, point> edge;
  14
  15 double euclidean(const point &a, const point &b){ return hypot(a.first-b.first, a.second-b.second);}
  16
  17
  18 int main(){
  19   int casos;
  20   cin >> casos;
  21   while (casos--){
  22     graph g;
  23     int n;
  24     cin >> n;
  25     while (n--){
  26       double x,y;
  27       cin >> x >> y;
  28       point p(x,y);
  29       if (g.count(p) == 0){ //Si no está todavía
  30         vector<point> v;
  31         g[p] = v;
  32         for (graph::iterator i = g.begin(); i != g.end(); ++i){
  33           if ((*i).first != p){
  34             (*i).second.push_back(p);
  35             g[p].push_back((*i).first);
  36           }
  37         }
  38       }
  39     }
  40
  41     set<point> visited;
  42     priority_queue<edge, vector<edge>, greater<edge> > q;
  43     //Each edge in q has got a length "first" and a point "second".
  44     //It means I can reach point "second" which is "first" meters away.
  45     //q has the closest reachable node on top (I may have already visited it!)
  46     q.push(edge(0.0, (*g.begin()).first));
  47     double totalDistance = 0.0;
  48     while (!q.empty()){
  49       edge nearest = q.top();
  50       q.pop();
  51       point actualNode = nearest.second;
  52       if (visited.count(actualNode) == 1) continue; //Ya habia visitado este
  53       totalDistance += nearest.first;
  54       visited.insert(actualNode);
  55       vector<point> neighbors = g[actualNode];
  56       for (int i=0; i<neighbors.size(); ++i){
  57         point t = neighbors[i];
  58         double dist = euclidean(actualNode, t);
  59         q.push(edge(dist, t));
  60       }
  61     }
  62     printf("%.2f\n", totalDistance);
  63     if (casos > 0) cout << endl; //Endl between cases
  64   }
  65 }